UTCTF recur Write Up

Details:

Points: 624

Jeopardy style CTF

Category: reverse engineering

Comment:

I found this binary that is supposed to print flags.

It doesn't seem to work properly though...

Write up:

Running the file we get the following output:

./recur 
utflag{

After this the program seems to keep chugging, if left for a bit of time we get one more letter, 0.

Next I checked what type of file it was and saw that it was a 64 bit ELF file. At this point I started reverse engineering.

The main function was:

int __cdecl main(int argc, const char **argv, const char **envp)
{
  char v3; // bl
  unsigned __int8 v4; // al
  int i; // [rsp+Ch] [rbp-14h]

  for ( i = 0; i <= 27; ++i )
  {
    v3 = flag[i];
    v4 = recurrence(i * i);
    putchar(v3 ^ v4);
    fflush(stdout);
  }
  return 0;
}

This loops through some flag value and then passes the current place squared to the recurrence function before xor'ing them together.

The recurrence function looked like this:

__int64 __fastcall recurrence(int a1)
{
  int v2; // ebx

  if ( !a1 )
    return 3LL;
  if ( a1 == 1 )
    return 5LL;
  v2 = 2 * recurrence(a1 - 1);
  return v2 + 3 * (unsigned int)recurrence(a1 - 2);
}

I then also looked at the values of flag:

flag = [0x76, 0x71, 0xC5, 0xA9, 0xE2, 0x22, 0xD8, 0xB5, 0x73, 0xF1, 0x92, 0x28, 0xB2, 0xBF, 0x90, 0x5A, 0x76, 0x77, 0xFC, 0xA6, 0xB3, 0x21, 0x90, 0xDA, 0x6F, 0xB5, 0xCF, 0x38]

As the purpose of this challenge was to complete this program I decided that to do this we would need to optimize the recurrence function. Rather than finding the same numbers over and over again I decided to store all found values in an array and return them. I decided to code this in python since I didn't want to deal with memory allocation in c.

# known flag values
flag = [0x76, 0x71, 0xC5, 0xA9, 0xE2, 0x22, 0xD8, 0xB5, 0x73, 0xF1, 0x92, 0x28, 0xB2, 0xBF, 0x90, 0x5A, 0x76, 0x77, 0xFC, 0xA6, 0xB3, 0x21, 0x90, 0xDA, 0x6F, 0xB5, 0xCF, 0x38]

# string to store flag in
s = ""

# known return values
nums = [3, 5]

# modified recurrence function
def recurrence(i):

    # if i is in the array then return the found value
    if i < len(nums):
        return nums[i]

    # otherwise do the normal stuff
    x = 2*recurrence(i-1)
    ret = x + 3* recurrence(i-2)

    # if i is the next number in the array then add it
    if i == len(nums):
        nums.append(ret)

    # return the value 
    return ret

# loop through the flag
for i in range(0,28):
    # loop through the values from i to i*i -1
	for j in range(i, i*i):
        # add all values to the array
		recurrence(j)
    # add value to string, we need to and the result of recurrence with 0xFF 
    # since char only accepts 2 hex values
	s += chr(flag[i]^(recurrence(i*i)&0xFF))

# print the string
print(s)

When run we get the flag:

utflag{0pt1m1z3_ur_c0d3_l0l}